package com.gxc.string;

import java.util.Iterator;
import java.util.TreeMap;

/**
 * 给你一个字符串类型的数组arr，
 * 譬如:String[] arr =["b\\cst"，"d\\"."a\\d\\e"."a\\b\\c"};
 * 你把这些路径中蕴含的目录结构给画出来，子目录直接列在父目录下面，并比父目录向右进两格，就像这样:
 * a
 * 	    b
 * 		    c
 * 	    d
 * 		    e
 * b
 * 	    cst
 * d
 * 同一级的需要按字母顺序排列，不能乱。
 *
 * 解法:
 * 1.设置一种树形结构 tree， int[26]  0...25 标识 a.......z，数组嵌套数组，浪费空间太大
 * 2.前缀树
 */
public class FormatPrint {

    public static void main(String[] args) {
        String[] arr =new String[]{"b\\\\cst", "d\\\\" ,"a\\\\d\\\\e" , "a\\\\b\\\\c"};
        print(arr);

        System.out.println("------------");
        String str = "b\\\\cst";
        String[] split = str.split("\\\\");
        for (int i = 0; i < split.length; i++) {
            System.out.println(split[i]);
        }
    }

    public static void print(String[] arr) {
        if (arr == null || arr.length == 0) return;

        TreeNode treeNode = generateTree(arr);
        treePrint(treeNode, 0);
    }

    /**
     * 树打印
     * @param treeNode
     * @param level
     */
    private static void treePrint(TreeNode treeNode, int level) {
        if (treeNode == null) return;

        //除了第一次不打印空格，第几层就打印几个空格
        if (level>1) {
            for (int i = 0; i < level; i++) {
                System.out.print(" ");
            }
        }
        System.out.println(treeNode.name);

        Iterator<TreeNode> iterator = treeNode.nextMap.values().iterator();
        while (iterator.hasNext()) {
            treePrint(iterator.next(), level+1);
        }
    }

    /**
     * 生成树
     * @param arr
     * @return
     */
    public static TreeNode generateTree(String[] arr) {
        TreeNode treeNode = new TreeNode("");

        TreeNode cur = null;
        for (int i = 0; i < arr.length; i++) {
            String str = arr[i];
            //每个字符串都的从头节点开始
            cur = treeNode;
            String[] split = str.split("\\\\");
            for (int j = 0; j < split.length; j++) {
                String s = split[j];
                if (s.equals("")) continue;
                //如果前缀树未添加过字符串，则添加
                if (!cur.nextMap.containsKey(s)) {
                    cur.nextMap.put(s, new TreeNode(s));
                }
                //下一个字符串的头结点是当前字符串
                cur = cur.nextMap.get(s);
            }
        }
        return treeNode;
    }

    public static class TreeNode {

        public String name;
        public TreeMap<String, TreeNode> nextMap;

        public TreeNode(String name) {
            this.name = name;
            nextMap = new TreeMap<>();
        }
    }

}
